package 二叉树.二叉搜索树的第K大节点;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2023/3/16 17:07
 * @description:
 * @version:
 */
public class Solution {
    public static void main(String[] args) {
        TreeNode head = new TreeNode(3,new TreeNode(1,null,new TreeNode(2)),new TreeNode(4));
        int i = kthLargest(head, 1);
        System.out.println(i);
    }


    //中序遍历即可
    public static int kthLargest(TreeNode root, int k) {
        List<Integer> list = new ArrayList<>();
        inOrder(root,list);
        Integer integer = list.get(list.size() - k);
        int count = 1;
        return integer;
    }

    //中序遍历
    public static void inOrder(TreeNode head,List<Integer> list){
        if (head == null){
            return ;
        }
        inOrder(head.left,list);
        list.add(head.val);
        inOrder(head.right,list);
    }


    //TODO 未完待续
    //优化思路，这里求第K大的值，所有可采用右中左的遍历方式，再新增一个全局变量，即可提前返回。
    public static Integer inOrder2(TreeNode head,List<Integer> list,Integer count,Integer target){
        if (head == null){
            return -1;
        }
        if (count == target){
            return head.val;
        }
        inOrder2(head.right,list,count,target);
        list.add(head.val);
        inOrder2(head.left,list,count,target);
        return -1;
    }



}
